package br.com.rookgraph.branchreduce;

import br.com.rookgraph.Edge;
import br.com.rookgraph.Graph;
import br.com.rookgraph.Swap;
import br.com.rookgraph.heuristica.Algoritm;
import br.com.rookgraph.heuristica.NotEstanque;
import br.com.rookgraph.utils.ArrayUtils;



public class BranchReduceNotEstanque implements Algoritm{
	// public class BranchReduceNotEstanque extends NotEstanque{
	/**
	 * @param args
	 */
	private Graph original;
	private Graph tree;
	private NotEstanque heuristica;

	public BranchReduceNotEstanque (Graph original, Graph tree, NotEstanque heuristica) {								 
		super();
		this.original = original;
		this.tree = tree;
		this.heuristica = heuristica;
	}

    @Override
	public Graph execute() {
		Graph graphBest = this.tree;
//		boolean isChange, trocou;
		Swap bestSwap = null, lastSwap = null, candidate;//, candidata;
		int i, grauMaxGraph;
		
		grauMaxGraph = original.getGrauMax(original);
		
		System.out.println(" GrauMax ==> "+ grauMaxGraph);
		i = 0;
//		Swap lastCut = null;
		
		do {
//		    trocou = false;	
			Edge[] listCut = createCuttingList();
			Edge[] listRep;
			
			bestSwap = null;
			
			for (Edge edgeCut : listCut) {

				this.tree.removeEdge(edgeCut);

				listRep = createReplacementListToCuttingEdge(edgeCut);			
	
			    this.tree.addEdge(edgeCut);
 							    
			    for (Edge edgeRep : listRep) {
					candidate = new Swap(edgeCut, edgeRep);
				//	bestSwap = bestSwap == null? candidate : bestSwap;
				//	if(bestSwap != null && !candidate.equals(new Swap(bestSwap.getReplace(), bestSwap.getCut()))){
					//if(!candidate.equals(new Swap(bestSwap.getReplace(), bestSwap.getCut()))){
						if(this.heuristica.isBest(tree,candidate,bestSwap)){
							bestSwap = candidate;
						}	
				//	}
				}				
			}
			
			if (bestSwap != null) { 
			    //System.out.println("bestSwap: "+ bestSwap);
				this.tree.swapEdge(bestSwap);
			
				if(lastSwap != null){
					if(lastSwap.equals(new Swap(bestSwap.getReplace(),bestSwap.getCut()))){
						bestSwap = null;
					}
				}
								
				if (isTreeBest(graphBest)) {
					try {
						graphBest = (Graph) this.tree.clone();
					} catch (CloneNotSupportedException e) {
						e.printStackTrace();
					}
				}else{
					 if (i >= original.getOrder()){
					//if (i >= grauMaxGraph){
						bestSwap = null;		
					}
					i++;
			//System.out.println(" I ==> "+ i);
				}
                 
				if(bestSwap != null){     // Atualiza a lastswap
					try {
						lastSwap = (Swap) bestSwap.clone();
					} catch (CloneNotSupportedException e) {
						e.printStackTrace();
					}
				}
			}
		} 
		while (bestSwap != null);
 		
		//System.out.println(" GrauMax ==> "+ grauMaxGraph);
		return graphBest;	
	}


	
	public boolean isTreeBest(Graph graphBest) {
		return this.tree.getBranchs().length < graphBest.getBranchs().length;
	}

	public void calcParameters(Edge edge, boolean insert) {
		if(edge != null){
			edge.alfa = this.tree.alfa(edge);
			edge.sigma = this.tree.sigma(edge);
			edge.beta = this.tree.beta(edge, insert);
			edge.gama = this.tree.gama(edge, insert);
			edge.sigmaLine = this.original.sigma(edge);	
		}
	}

	protected Edge[] createReplacementListToCuttingEdge(final Edge arestaCut) {

		int[] seg1 = this.tree.reached(arestaCut.origin, new int[this.tree.getOrder()]);
		int[] seg2 = this.tree.reached(arestaCut.target, new int[this.tree.getOrder()]);

		// TODO verificar tamanho dessa lista por um teorema.
		Edge[] arestasRep = new Edge[seg1.length * seg2.length];

		int count = 0;

		/* Comparar arestas dos segmentos com as do grafo original */
		for (int vSeg1 : seg1) {
			for (int vSeg2 : seg2) {

				final Edge currentArest = new Edge(vSeg1, vSeg2);

				// if (!currentArest.equals(arestaCut) {  na heuritisca original a linha é essa
				if (!currentArest.equals(arestaCut) && (this.original.grau(vSeg1) > 1 && this.original.grau(vSeg2) > 1)) {

					if (!this.tree.hasEdge(vSeg1, vSeg2) && this.original.hasEdge(vSeg1, vSeg2)) {
                        
						//  veio para cá
						
					    this.tree.addEdge(currentArest);

						calcParameters(currentArest, true);

						this.tree.removeEdge(currentArest);

						if (!ArrayUtils.contains(currentArest, arestasRep)){
							arestasRep[count++] = currentArest;
						}
					}
				}
			}
		}

		Edge[] listRep = new Edge[count];
		System.arraycopy(arestasRep, 0, listRep, 0, count);

		return listRep;
	}

	/**
	 * Cria a lista de arestas candidatas a corte.
	 *
	 * @return
	 */
	protected Edge[] createCuttingList() {
		int order = tree.getOrder();
		int count = 0;
		Edge[] edgesCut = new Edge[order * order];

		for (int branch : this.tree.getBranchs()) {
			for (int adjacente : this.tree.getAdjacentes(branch)) {

				Edge candidata = new Edge(branch, adjacente);

				// if (!conteins(candidata, edgesCut)) { na algoritimo original a linha é essa
				if (!ArrayUtils.contains(candidata, edgesCut)  && (this.original.grau(adjacente) > 1)){
					calcParameters(candidata, false);
					edgesCut[count++] = candidata;
				}
			}
		}

		Edge[] listCut = new Edge[count];
		System.arraycopy(edgesCut, 0, listCut, 0, count);
		return listCut;
	}

		
	public Graph getOriginal() {
		return original;
	}

	public void setOriginal(Graph original) {
		this.original = original;
	}

	public Graph getTree() {
		return tree;
	}

	public void setTree(Graph tree) {
		this.tree = tree;
	}

}
